#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <fstream>
using namespace std;
struct Vertex{int id;string name;int trafficFlow;};
struct Edge{int from,to,length,time,maxVehicles;bool available;int initTime,initMaxVehicles;};
struct TrafficEvent{int eventId,vertexId;string type;int affectRange,affectTime,recoverTime;};
struct Car{int id,start,end,departTime;};
class Graph{
public:
    unordered_map<int,Vertex> vertices;
    unordered_map<int,vector<Edge>> adj;
    void addVertex(int id,const string& name){vertices[id]={id,name,0};}
    void addEdge(int f,int t,int l,int ti,int m){adj[f].push_back({f,t,l,ti,m,1,ti,m});adj[t].push_back({t,f,l,ti,m,1,ti,m});}
    void dfs(int s,unordered_map<int,bool>& v){v[s]=1;cout<<"DFS visit: "<<s<<endl;for(auto&e:adj[s])if(!v[e.to])dfs(e.to,v);}
    void bfs(int s){unordered_map<int,bool>v;queue<int>q;q.push(s);v[s]=1;while(!q.empty()){int u=q.front();q.pop();cout<<"BFS visit: "<<u<<endl;for(auto&e:adj[u])if(!v[e.to])v[e.to]=1,q.push(e.to);}}
    int getEventTimeDelta(const string&t){if(t=="accident"||t=="major_accident")return 20;if(t=="construction")return 15;if(t=="traffic_jam")return 10;if(t=="weather")return 25;return 10;}
    void applyEvents(const vector<TrafficEvent>&ev,int cur){for(auto&[f,es]:adj)for(auto&e:es)e.time=e.initTime,e.maxVehicles=e.initMaxVehicles,e.available=1;for(const auto&e:ev)if(e.affectTime<=cur&&cur<e.recoverTime){int d=getEventTimeDelta(e.type);for(auto&ed:adj[e.vertexId])if(e.type=="road_closure"||e.type=="major_accident")ed.available=0,ed.maxVehicles=0,ed.time+=(e.type=="major_accident"?d:0);else if(e.type=="minor_accident")ed.time+=d,ed.maxVehicles=min(ed.maxVehicles,3);else if(e.type=="traffic_jam")ed.time+=d,ed.maxVehicles=min(ed.maxVehicles,2);else if(e.type=="weather")ed.time+=d,ed.maxVehicles=min(ed.maxVehicles,8);else if(e.type=="police_control")ed.time+=d,ed.maxVehicles=min(ed.maxVehicles,6);else if(e.type=="construction")ed.time+=d,ed.maxVehicles=min(ed.maxVehicles,4);else ed.time+=d,ed.maxVehicles=min(ed.maxVehicles,5);}}
    vector<int> dijkstra(int src,int dst,const vector<TrafficEvent>&ev,int cur){
        unordered_map<int,int>dist,prev,maxCap;
        for(auto&v:vertices)dist[v.first]=INT_MAX,maxCap[v.first]=0;
        dist[src]=0,maxCap[src]=INT_MAX;
        using P=pair<int,int>;
        priority_queue<P,vector<P>,greater<P>>pq;
        pq.push({0,src});
        while(!pq.empty()){
            auto[d,u]=pq.top();pq.pop();
            if(u==dst)break;
            for(auto&e:adj[u]){
                if(!e.available)continue;
                int t=e.time,c=e.maxVehicles;
                for(const auto&evn:ev)if(evn.affectTime<=cur&&cur<evn.recoverTime&&evn.vertexId==e.to){int d=getEventTimeDelta(evn.type);if(evn.type=="road_closure"){c=0;t=INT_MAX;break;}if(evn.type=="major_accident"){t+=d;c=0;break;}if(evn.type=="minor_accident")t+=d,c=min(c,3);else if(evn.type=="traffic_jam")t+=d,c=min(c,2);else if(evn.type=="weather")t+=d,c=min(c,8);else if(evn.type=="police_control")t+=d,c=min(c,6);else if(evn.type=="construction")t+=d,c=min(c,4);else t+=d,c=min(c,5);}
                if(t==INT_MAX||c==0)continue;
                if(dist[e.to]>dist[u]+t){dist[e.to]=dist[u]+t;prev[e.to]=u;maxCap[e.to]=min(maxCap[u],c);pq.push({dist[e.to],e.to});}
                else if(dist[e.to]==dist[u]+t){int nc=min(maxCap[u],c);if(nc>maxCap[e.to])prev[e.to]=u,maxCap[e.to]=nc;}
            }
        }
        vector<int>path;if(dist[dst]==INT_MAX)return path;for(int at=dst;prev.count(at);at=prev[at])path.push_back(at);path.push_back(src);reverse(path.begin(),path.end());return path;
    }
    vector<Vertex> sortTrafficFlow(){vector<Vertex>v;for(auto&p:vertices)v.push_back(p.second);sort(v.begin(),v.end(),[](const Vertex&a,const Vertex&b){return a.trafficFlow>b.trafficFlow;});return v;}
    void visualize(){
        cout<<"\n========== 城市交通网络地图 ==========\n";
        for(const auto&v:vertices){
            cout<<"路口 "<<v.first<<" ["<<v.second.name<<"]\n  └─ 连通道路：\n";
            if(adj[v.first].empty())cout<<"      (无)\n";
            for(const auto&e:adj[v.first])cout<<"      → 路口 "<<e.to<<" ["<<vertices[e.to].name<<"] | 长度: "<<e.length<<" | 时间: "<<e.time<<" | 最大承载: "<<e.maxVehicles<<"\n";
            cout<<"--------------------------------------\n";
        }
        cout<<"======================================\n";
    }
};
class EventQueue{
public:
    queue<TrafficEvent>q;vector<TrafficEvent>activeEvents;
    void addEvent(const TrafficEvent&e){q.push(e);}
    void processEvents(int cur){while(!q.empty()&&q.front().affectTime<=cur)activeEvents.push_back(q.front()),q.pop();}
    void cleanEvents(int cur){activeEvents.erase(remove_if(activeEvents.begin(),activeEvents.end(),[cur](const TrafficEvent&e){return e.recoverTime<=cur;}),activeEvents.end());}
    const vector<TrafficEvent>& getActiveEvents()const{return activeEvents;}
};
void dfs_print(int s,unordered_map<int,bool>&v,Graph&g,ostream&out){v[s]=1;out<<"DFS visit: "<<s<<endl;for(const auto&e:g.adj[s])if(!v[e.to])dfs_print(e.to,v,g,out);}
void bfs_print(int s,Graph&g,ostream&out){unordered_map<int,bool>v;queue<int>q;q.push(s);v[s]=1;while(!q.empty()){int u=q.front();q.pop();out<<"BFS visit: "<<u<<endl;for(const auto&e:g.adj[u])if(!v[e.to])v[e.to]=1,q.push(e.to);}}
int main(){
    Graph g;EventQueue eq;
    ifstream fin("test_input.txt");istream&in=fin.is_open()?fin:cin;
    ofstream fout("output.txt");ostream&out=fout.is_open()?fout:cout;
    int vnum,edgenum,eventnum;in>>vnum;
    for(int i=1;i<=vnum;++i){string name;in>>name;g.addVertex(i,name);}
    in>>edgenum;
    for(int i=0;i<edgenum;++i){int f,t,l,ti,m;in>>f>>t>>l>>ti>>m;g.addEdge(f,t,l,ti,m);}
    in>>eventnum;
    for(int i=0;i<eventnum;++i){int eid,vid,ar,at,rt;string type;in>>eid>>vid>>type>>ar>>at>>rt;eq.addEvent({eid,vid,type,ar,at,rt});}
    int cur;in>>cur;
    vector<Car>cars;int carNum=0;
    if(in>>carNum){for(int i=0;i<carNum;++i){Car car;car.id=i+1;in>>car.start>>car.end>>car.departTime;cars.push_back(car);}}
    else{in.clear();in.seekg(0,ios::beg);for(int skip=0;skip<vnum+1+edgenum*5+1+eventnum*6+1;++skip)in>>ws;int src,dst;in>>src>>dst;cars.push_back({1,src,dst,cur});}
    for(const auto&car:cars){
        eq.processEvents(car.departTime);eq.cleanEvents(car.departTime);g.applyEvents(eq.getActiveEvents(),car.departTime);
        vector<int>path=g.dijkstra(car.start,car.end,eq.getActiveEvents(),car.departTime);
        out<<"车辆"<<car.id<<" 最短路径: ";for(int v:path)out<<v<<" ";out<<endl;
        for(int v:path)g.vertices[v].trafficFlow++;
        unordered_map<int,bool>vdfs;out<<"车辆"<<car.id<<" DFS:"<<endl;dfs_print(car.start,vdfs,g,out);
        out<<"车辆"<<car.id<<" BFS:"<<endl;bfs_print(car.start,g,out);
    }
    auto sorted=g.sortTrafficFlow();out<<"流量排序: ";for(auto&v:sorted)out<<v.id<<"("<<v.trafficFlow<<") ";out<<endl;
    out<<"\n========== 城市交通网络地图 ==========\n";
    for(const auto&v:g.vertices){
        out<<"路口 "<<v.first<<" ["<<v.second.name<<"]\n  └─ 连通道路：\n";
        if(g.adj[v.first].empty())out<<"      (无)\n";
        for(const auto&e:g.adj[v.first])out<<"      → 路口 "<<e.to<<" ["<<g.vertices[e.to].name<<"] | 长度: "<<e.length<<" | 时间: "<<e.time<<" | 最大承载: "<<e.maxVehicles<<"\n";
        out<<"--------------------------------------\n";
    }
    out<<"======================================\n";
    {
        ifstream fin("output.txt");ofstream html("output_viewer.html");
        html<<"<!DOCTYPE html><html lang=\"zh-cn\"><head><meta charset=\"UTF-8\"><title>交通网络输出可视化</title>\n";
        html<<R"(<style>
body{font-family:'微软雅黑',Arial,sans-serif;background:linear-gradient(120deg,#f7f7f7 60%,#e3e9f7 100%);margin:0;}
.main-container{max-width:900px;margin:32px auto;padding:24px 18px 32px 18px;background:#fff;border-radius:18px;box-shadow:0 6px 32px 0 rgba(44,62,80,0.10),0 1.5px 4px 0 rgba(44,62,80,0.06);}
h1{text-align:center;color:#34495e;margin-bottom:32px;letter-spacing:2px;}
h2{color:#2c3e50;border-left:5px solid #6c63ff;padding-left:10px;margin-top:0;margin-bottom:18px;font-size:1.3em;}
.section{background:#f8fafd;border-radius:12px;margin-bottom:28px;padding:18px 18px 10px 18px;box-shadow:0 1px 6px #e3e9f7;}
.section:hover{box-shadow:0 4px 16px #d1d8e6;}
.car-block{margin-bottom:18px;padding:12px 14px;background:#f3f4fa;border-radius:8px;box-shadow:0 1px 4px #e3e9f7;}
.car-title{color:#6c63ff;font-weight:bold;margin-bottom:8px;}
.car-sub{color:#888;font-size:0.98em;margin-bottom:6px;}
table{border-collapse:collapse;width:100%;margin-top:8px;background:#fff;border-radius:8px;overflow:hidden;box-shadow:0 1px 4px #e3e9f7;}
th,td{border:none;padding:8px 12px;text-align:left;}
th{background:#6c63ff;color:#fff;font-weight:500;}
tr:nth-child(even) td{background:#f3f4fa;}
.map-block{margin-bottom:14px;background:#f3f4fa;border-radius:8px;padding:10px 12px;box-shadow:0 1px 4px #e3e9f7;}
.road-list{margin-left:24px;margin-bottom:0;padding-left:0;}
.road-list li{margin-bottom:2px;list-style:disc;}
.highlight{color:#e67e22;font-weight:bold;font-size:1.1em;}
@media (max-width:600px){.main-container{padding:8px 2px;}h1{font-size:1.2em;}h2{font-size:1em;}}
</style>)";
        html<<"</head><body><div class=\"main-container\"><h1>交通网络输出可视化</h1>\n";
        html<<"<div class=\"section\" style=\"display:none\"><pre id=\"raw\">";
        string line,all;while(getline(fin,line))html<<line<<"\\n",all+=line+"\n";
        html<<"</pre></div><div id=\"content\"></div>\n";
        html<<R"(<script>
function renderOutput(text){
    const c=document.getElementById('content');
    c.innerHTML='';
    let carBlocks=[],carRe=/车辆(\d+)\s*最短路径:\s*([^\n]*)[\r\n]+车辆\1\s*DFS:[\r\n]+((?:DFS visit:.*[\r\n]+)+)车辆\1\s*BFS:[\r\n]+((?:BFS visit:.*[\r\n]+)+)/g,carMatch;
    while((carMatch=carRe.exec(text))!==null){
        let carId=carMatch[1],path=carMatch[2].trim().split(/\s+/),dfsLines=carMatch[3].trim().split('\n').filter(l=>l.trim()),bfsLines=carMatch[4].trim().split('\n').filter(l=>l.trim());
        carBlocks.push(`<div class='car-block'><div class='car-title'>车辆${carId} 最短路径</div><div class='car-sub'>路径节点：<span class='highlight'>${path.join(' <span style="color:#6c63ff;font-weight:bold;">→</span> ')}</span></div><div class='car-sub'>DFS遍历：</div><ul style="margin-left:18px;">${dfsLines.map(l=>`<li>${l}</li>`).join('')}</ul><div class='car-sub'>BFS遍历：</div><ul style="margin-left:18px;">${bfsLines.map(l=>`<li>${l}</li>`).join('')}</ul></div>`);
    }
    if(carBlocks.length)c.innerHTML+=`<div class='section'><h2>各车辆路径与遍历</h2>${carBlocks.join('')}</div>`;
    else{
        let m=text.match(/最短路径:([^\n]*)/),d=text.match(/DFS:\s*([\s\S]*?)BFS:/),b=text.match(/BFS:\s*([\s\S]*?)(流量排序:|={10,}|$)/);
        if(m){let path=m[1].trim().split(/\s+/);c.innerHTML+=`<div class='section'><h2>最短路径</h2><div>路径节点：<span class='highlight'>${path.join(' <span style="color:#6c63ff;font-weight:bold;">→</span> ')}</span></div></div>`;}
        if(d){let dfsLines=d[1].trim().split('\n').filter(Boolean);c.innerHTML+=`<div class='section'><h2>DFS遍历</h2><ul style="margin-left:18px;">${dfsLines.map(l=>`<li>${l}</li>`).join('')}</ul></div>`;}
        if(b){let bfsLines=b[1].trim().split('\n').filter(Boolean);c.innerHTML+=`<div class='section'><h2>BFS遍历</h2><ul style="margin-left:18px;">${bfsLines.map(l=>`<li>${l}</li>`).join('')}</ul></div>`;}
    }
    let f=text.match(/流量排序:([^\n]*)/);
    if(f){
        let flows=f[1].trim().split(/\s+/).map(s=>{let m=s.match(/(\d+)\((\d+)\)/);return m?{id:m[1],flow:m[2]}:null;}).filter(Boolean);
        let table='<table><tr><th>路口ID</th><th>流量</th></tr>';
        flows.forEach(f=>table+=`<tr><td>${f.id}</td><td>${f.flow}</td></tr>`);table+='</table>';
        c.innerHTML+=`<div class='section'><h2>流量排序</h2>${table}</div>`;
    }
    let map=text.match(/={10,}[\s\S]*={10,}/);
    if(map){
        let mapLines=map[0].split('\n').slice(1,-1),html2='',block='';
        mapLines.forEach(line=>{
            if(line.startsWith('路口')){
                if(block)html2+=`<div class='map-block'>${block}</div>`;
                block=`<strong style="color:#6c63ff">${line}</strong><ul class='road-list'>`;
            }else if(line.startsWith('      →'))block+=`<li>${line.trim()}</li>`;
            else if(line.includes('无'))block+=`<li style="color:#aaa">${line.trim()}</li>`;
            else if(line.startsWith('---'))block+='</ul>';
        });
        if(block)html2+=`<div class='map-block'>${block}</div>`;
        c.innerHTML+=`<div class='section'><h2>城市交通网络地图</h2>${html2}</div>`;
    }
}
window.onload=function(){
    var raw=document.getElementById('raw').innerText.replace(/\\n/g,'\n');
    renderOutput(raw);
};
</script>)";
        html<<"</div></body></html>\n";
    }
    return 0;
}